home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_slist.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  31.5 KB  |  1,049 lines
  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  */
  14.  
  15. /* NOTE: This is an internal header file, included by other STL headers.
  16.  *   You should not attempt to use it directly.
  17.  */
  18.  
  19. #ifndef __SGI_STL_INTERNAL_SLIST_H
  20. #define __SGI_STL_INTERNAL_SLIST_H
  21.  
  22. #include <concept_checks.h>
  23.  
  24. __STL_BEGIN_NAMESPACE 
  25.  
  26. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  27. #pragma set woff 1174
  28. #pragma set woff 1375
  29. #endif
  30.  
  31. struct _Slist_node_base
  32. {
  33.   _Slist_node_base* _M_next;
  34. };
  35.  
  36. inline _Slist_node_base*
  37. __slist_make_link(_Slist_node_base* __prev_node,
  38.                   _Slist_node_base* __new_node)
  39. {
  40.   __new_node->_M_next = __prev_node->_M_next;
  41.   __prev_node->_M_next = __new_node;
  42.   return __new_node;
  43. }
  44.  
  45. inline _Slist_node_base* 
  46. __slist_previous(_Slist_node_base* __head,
  47.                  const _Slist_node_base* __node)
  48. {
  49.   while (__head && __head->_M_next != __node)
  50.     __head = __head->_M_next;
  51.   return __head;
  52. }
  53.  
  54. inline const _Slist_node_base* 
  55. __slist_previous(const _Slist_node_base* __head,
  56.                  const _Slist_node_base* __node)
  57. {
  58.   while (__head && __head->_M_next != __node)
  59.     __head = __head->_M_next;
  60.   return __head;
  61. }
  62.  
  63. inline void __slist_splice_after(_Slist_node_base* __pos,
  64.                                  _Slist_node_base* __before_first,
  65.                                  _Slist_node_base* __before_last)
  66. {
  67.   if (__pos != __before_first && __pos != __before_last) {
  68.     _Slist_node_base* __first = __before_first->_M_next;
  69.     _Slist_node_base* __after = __pos->_M_next;
  70.     __before_first->_M_next = __before_last->_M_next;
  71.     __pos->_M_next = __first;
  72.     __before_last->_M_next = __after;
  73.   }
  74. }
  75.  
  76. inline void
  77. __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
  78. {
  79.   _Slist_node_base* __before_last = __slist_previous(__head, 0);
  80.   if (__before_last != __head) {
  81.     _Slist_node_base* __after = __pos->_M_next;
  82.     __pos->_M_next = __head->_M_next;
  83.     __head->_M_next = 0;
  84.     __before_last->_M_next = __after;
  85.   }
  86. }
  87.  
  88. inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
  89. {
  90.   _Slist_node_base* __result = __node;
  91.   __node = __node->_M_next;
  92.   __result->_M_next = 0;
  93.   while(__node) {
  94.     _Slist_node_base* __next = __node->_M_next;
  95.     __node->_M_next = __result;
  96.     __result = __node;
  97.     __node = __next;
  98.   }
  99.   return __result;
  100. }
  101.  
  102. inline size_t __slist_size(_Slist_node_base* __node)
  103. {
  104.   size_t __result = 0;
  105.   for ( ; __node != 0; __node = __node->_M_next)
  106.     ++__result;
  107.   return __result;
  108. }
  109.  
  110. template <class _Tp>
  111. struct _Slist_node : public _Slist_node_base
  112. {
  113.   _Tp _M_data;
  114. };
  115.  
  116. struct _Slist_iterator_base
  117. {
  118.   typedef size_t               size_type;
  119.   typedef ptrdiff_t            difference_type;
  120.   typedef forward_iterator_tag iterator_category;
  121.  
  122.   _Slist_node_base* _M_node;
  123.  
  124.   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
  125.   void _M_incr() { _M_node = _M_node->_M_next; }
  126.  
  127.   bool operator==(const _Slist_iterator_base& __x) const {
  128.     return _M_node == __x._M_node;
  129.   }
  130.   bool operator!=(const _Slist_iterator_base& __x) const {
  131.     return _M_node != __x._M_node;
  132.   }
  133. };
  134.  
  135. template <class _Tp, class _Ref, class _Ptr>
  136. struct _Slist_iterator : public _Slist_iterator_base
  137. {
  138.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  139.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  140.   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
  141.  
  142.   typedef _Tp              value_type;
  143.   typedef _Ptr             pointer;
  144.   typedef _Ref             reference;
  145.   typedef _Slist_node<_Tp> _Node;
  146.  
  147.   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
  148.   _Slist_iterator() : _Slist_iterator_base(0) {}
  149.   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
  150.  
  151.   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  152. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  153.   pointer operator->() const { return &(operator*()); }
  154. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  155.  
  156.   _Self& operator++()
  157.   {
  158.     _M_incr();
  159.     return *this;
  160.   }
  161.   _Self operator++(int)
  162.   {
  163.     _Self __tmp = *this;
  164.     _M_incr();
  165.     return __tmp;
  166.   }
  167. };
  168.  
  169. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  170.  
  171. inline ptrdiff_t* distance_type(const _Slist_iterator_base&) {
  172.   return 0;
  173. }
  174.  
  175. inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) {
  176.   return forward_iterator_tag();
  177. }
  178.  
  179. template <class _Tp, class _Ref, class _Ptr> 
  180. inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) {
  181.   return 0;
  182. }
  183.  
  184. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  185.  
  186. // Base class that encapsulates details of allocators.  Three cases:
  187. // an ordinary standard-conforming allocator, a standard-conforming
  188. // allocator with no non-static data, and an SGI-style allocator.
  189. // This complexity is necessary only because we're worrying about backward
  190. // compatibility and because we want to avoid wasting storage on an 
  191. // allocator instance if it isn't necessary.
  192.  
  193. #ifdef __STL_USE_STD_ALLOCATORS
  194.  
  195. // Base for general standard-conforming allocators.
  196. template <class _Tp, class _Allocator, bool _IsStatic>
  197. class _Slist_alloc_base {
  198. public:
  199.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  200.           allocator_type;
  201.   allocator_type get_allocator() const { return _M_node_allocator; }
  202.  
  203.   _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
  204.  
  205. protected:
  206.   _Slist_node<_Tp>* _M_get_node() 
  207.     { return _M_node_allocator.allocate(1); }
  208.   void _M_put_node(_Slist_node<_Tp>* __p) 
  209.     { _M_node_allocator.deallocate(__p, 1); }
  210.  
  211. protected:
  212.   typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
  213.            _M_node_allocator;
  214.   _Slist_node_base _M_head;
  215. };
  216.  
  217. // Specialization for instanceless allocators.
  218. template <class _Tp, class _Allocator>
  219. class _Slist_alloc_base<_Tp,_Allocator, true> {
  220. public:
  221.   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
  222.           allocator_type;
  223.   allocator_type get_allocator() const { return allocator_type(); }
  224.  
  225.   _Slist_alloc_base(const allocator_type&) {}
  226.  
  227. protected:
  228.   typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
  229.           _Alloc_type;
  230.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  231.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  232.  
  233. protected:
  234.   _Slist_node_base _M_head;
  235. };
  236.  
  237.  
  238. template <class _Tp, class _Alloc>
  239. struct _Slist_base
  240.   : public _Slist_alloc_base<_Tp, _Alloc,
  241.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  242. {
  243.   typedef _Slist_alloc_base<_Tp, _Alloc,
  244.                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  245.           _Base;
  246.   typedef typename _Base::allocator_type allocator_type;
  247.  
  248.   _Slist_base(const allocator_type& __a)
  249.     : _Base(__a) { this->_M_head._M_next = 0; }
  250.   ~_Slist_base() { _M_erase_after(&this->_M_head, 0); }
  251.  
  252. protected:
  253.  
  254.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  255.   {
  256.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  257.     _Slist_node_base* __next_next = __next->_M_next;
  258.     __pos->_M_next = __next_next;
  259.     destroy(&__next->_M_data);
  260.     _M_put_node(__next);
  261.     return __next_next;
  262.   }
  263.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  264. };
  265.  
  266. #else /* __STL_USE_STD_ALLOCATORS */
  267.  
  268. template <class _Tp, class _Alloc> 
  269. struct _Slist_base {
  270.   typedef _Alloc allocator_type;
  271.   allocator_type get_allocator() const { return allocator_type(); }
  272.  
  273.   _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
  274.   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
  275.  
  276. protected:
  277.   typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;
  278.   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  279.   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
  280.  
  281.   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
  282.   {
  283.     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
  284.     _Slist_node_base* __next_next = __next->_M_next;
  285.     __pos->_M_next = __next_next;
  286.     destroy(&__next->_M_data);
  287.     _M_put_node(__next);
  288.     return __next_next;
  289.   }
  290.   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
  291.  
  292. protected:
  293.   _Slist_node_base _M_head;
  294. };  
  295.  
  296. #endif /* __STL_USE_STD_ALLOCATORS */
  297.  
  298. template <class _Tp, class _Alloc> 
  299. _Slist_node_base*
  300. _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
  301.                                         _Slist_node_base* __last_node) {
  302.   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
  303.   while (__cur != __last_node) {
  304.     _Slist_node<_Tp>* __tmp = __cur;
  305.     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
  306.     destroy(&__tmp->_M_data);
  307.     _M_put_node(__tmp);
  308.   }
  309.   __before_first->_M_next = __last_node;
  310.   return __last_node;
  311. }
  312.  
  313. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  314. class slist : private _Slist_base<_Tp,_Alloc>
  315. {
  316.   // requirements:
  317.  
  318.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  319.  
  320. private:
  321.   typedef _Slist_base<_Tp,_Alloc> _Base;
  322. public:
  323.   typedef _Tp                value_type;
  324.   typedef value_type*       pointer;
  325.   typedef const value_type* const_pointer;
  326.   typedef value_type&       reference;
  327.   typedef const value_type& const_reference;
  328.   typedef size_t            size_type;
  329.   typedef ptrdiff_t         difference_type;
  330.  
  331.   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
  332.   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  333.  
  334.   typedef typename _Base::allocator_type allocator_type;
  335.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  336.  
  337. private:
  338.   typedef _Slist_node<_Tp>      _Node;
  339.   typedef _Slist_node_base      _Node_base;
  340.   typedef _Slist_iterator_base  _Iterator_base;
  341.  
  342.   _Node* _M_create_node(const value_type& __x) {
  343.     _Node* __node = this->_M_get_node();
  344.     __STL_TRY {
  345.       construct(&__node->_M_data, __x);
  346.       __node->_M_next = 0;
  347.     }
  348.     __STL_UNWIND(this->_M_put_node(__node));
  349.     return __node;
  350.   }
  351.   
  352.   _Node* _M_create_node() {
  353.     _Node* __node = this->_M_get_node();
  354.     __STL_TRY {
  355.       construct(&__node->_M_data);
  356.       __node->_M_next = 0;
  357.     }
  358.     __STL_UNWIND(this->_M_put_node(__node));
  359.     return __node;
  360.   }
  361.  
  362. public:
  363.   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
  364.  
  365.   slist(size_type __n, const value_type& __x,
  366.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  367.     { _M_insert_after_fill(&this->_M_head, __n, __x); }
  368.  
  369.   explicit slist(size_type __n) : _Base(allocator_type())
  370.     { _M_insert_after_fill(&this->_M_head, __n, value_type()); }
  371.  
  372. #ifdef __STL_MEMBER_TEMPLATES
  373.   // We don't need any dispatching tricks here, because _M_insert_after_range
  374.   // already does them.
  375.   template <class _InputIterator>
  376.   slist(_InputIterator __first, _InputIterator __last,
  377.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  378.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  379.  
  380. #else /* __STL_MEMBER_TEMPLATES */
  381.   slist(const_iterator __first, const_iterator __last,
  382.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  383.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  384.   slist(const value_type* __first, const value_type* __last,
  385.         const allocator_type& __a =  allocator_type()) : _Base(__a)
  386.     { _M_insert_after_range(&this->_M_head, __first, __last); }
  387. #endif /* __STL_MEMBER_TEMPLATES */
  388.  
  389.   slist(const slist& __x) : _Base(__x.get_allocator())
  390.     { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }
  391.  
  392.   slist& operator= (const slist& __x);
  393.  
  394.   ~slist() {}
  395.  
  396. public:
  397.   // assign(), a generalized assignment member function.  Two
  398.   // versions: one that takes a count, and one that takes a range.
  399.   // The range version is a member template, so we dispatch on whether
  400.   // or not the type is an integer.
  401.  
  402.   void assign(size_type __n, const _Tp& __val)
  403.     { _M_fill_assign(__n, __val); }
  404.  
  405.   void _M_fill_assign(size_type __n, const _Tp& __val);
  406.  
  407.  
  408. #ifdef __STL_MEMBER_TEMPLATES
  409.  
  410.   template <class _InputIterator>
  411.   void assign(_InputIterator __first, _InputIterator __last) {
  412.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  413.     _M_assign_dispatch(__first, __last, _Integral());
  414.   }
  415.  
  416.   template <class _Integer>
  417.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  418.     { _M_fill_assign((size_type) __n, (_Tp) __val); }
  419.  
  420.   template <class _InputIterator>
  421.   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  422.                           __false_type);
  423.  
  424. #endif /* __STL_MEMBER_TEMPLATES */
  425.  
  426. public:
  427.  
  428.   iterator begin() { return iterator((_Node*)this->_M_head._M_next); }
  429.   const_iterator begin() const 
  430.     { return const_iterator((_Node*)this->_M_head._M_next);}
  431.  
  432.   iterator end() { return iterator(0); }
  433.   const_iterator end() const { return const_iterator(0); }
  434.  
  435.   // Experimental new feature: before_begin() returns a
  436.   // non-dereferenceable iterator that, when incremented, yields
  437.   // begin().  This iterator may be used as the argument to
  438.   // insert_after, erase_after, etc.  Note that even for an empty 
  439.   // slist, before_begin() is not the same iterator as end().  It 
  440.   // is always necessary to increment before_begin() at least once to
  441.   // obtain end().
  442.   iterator before_begin() { return iterator((_Node*) &this->_M_head); }
  443.   const_iterator before_begin() const
  444.     { return const_iterator((_Node*) &this->_M_head); }
  445.  
  446.   size_type size() const { return __slist_size(this->_M_head._M_next); }
  447.   
  448.   size_type max_size() const { return size_type(-1); }
  449.  
  450.   bool empty() const { return this->_M_head._M_next == 0; }
  451.  
  452.   void swap(slist& __x)
  453.     { __STD::swap(this->_M_head._M_next, __x._M_head._M_next); }
  454.  
  455. public:
  456.  
  457.   reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; }
  458.   const_reference front() const 
  459.     { return ((_Node*) this->_M_head._M_next)->_M_data; }
  460.   void push_front(const value_type& __x)   {
  461.     __slist_make_link(&this->_M_head, _M_create_node(__x));
  462.   }
  463.   void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); }
  464.   void pop_front() {
  465.     _Node* __node = (_Node*) this->_M_head._M_next;
  466.     this->_M_head._M_next = __node->_M_next;
  467.     destroy(&__node->_M_data);
  468.     this->_M_put_node(__node);
  469.   }
  470.  
  471.   iterator previous(const_iterator __pos) {
  472.     return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node));
  473.   }
  474.   const_iterator previous(const_iterator __pos) const {
  475.     return const_iterator((_Node*) __slist_previous(&this->_M_head,
  476.                                                     __pos._M_node));
  477.   }
  478.  
  479. private:
  480.   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
  481.     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
  482.   }
  483.  
  484.   _Node* _M_insert_after(_Node_base* __pos) {
  485.     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
  486.   }
  487.  
  488.   void _M_insert_after_fill(_Node_base* __pos,
  489.                             size_type __n, const value_type& __x) {
  490.     for (size_type __i = 0; __i < __n; ++__i)
  491.       __pos = __slist_make_link(__pos, _M_create_node(__x));
  492.   }
  493.  
  494. #ifdef __STL_MEMBER_TEMPLATES
  495.  
  496.   // Check whether it's an integral type.  If so, it's not an iterator.
  497.   template <class _InIter>
  498.   void _M_insert_after_range(_Node_base* __pos, 
  499.                              _InIter __first, _InIter __last) {
  500.     typedef typename _Is_integer<_InIter>::_Integral _Integral;
  501.     _M_insert_after_range(__pos, __first, __last, _Integral());
  502.   }
  503.  
  504.   template <class _Integer>
  505.   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
  506.                              __true_type) {
  507.     _M_insert_after_fill(__pos, __n, __x);
  508.   }
  509.  
  510.   template <class _InIter>
  511.   void _M_insert_after_range(_Node_base* __pos,
  512.                              _InIter __first, _InIter __last,
  513.                              __false_type) {
  514.     while (__first != __last) {
  515.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  516.       ++__first;
  517.     }
  518.   }
  519.  
  520. #else /* __STL_MEMBER_TEMPLATES */
  521.  
  522.   void _M_insert_after_range(_Node_base* __pos,
  523.                              const_iterator __first, const_iterator __last) {
  524.     while (__first != __last) {
  525.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  526.       ++__first;
  527.     }
  528.   }
  529.   void _M_insert_after_range(_Node_base* __pos,
  530.                              const value_type* __first,
  531.                              const value_type* __last) {
  532.     while (__first != __last) {
  533.       __pos = __slist_make_link(__pos, _M_create_node(*__first));
  534.       ++__first;
  535.     }
  536.   }
  537.  
  538. #endif /* __STL_MEMBER_TEMPLATES */
  539.  
  540. public:
  541.  
  542.   iterator insert_after(iterator __pos, const value_type& __x) {
  543.     return iterator(_M_insert_after(__pos._M_node, __x));
  544.   }
  545.  
  546.   iterator insert_after(iterator __pos) {
  547.     return insert_after(__pos, value_type());
  548.   }
  549.  
  550.   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
  551.     _M_insert_after_fill(__pos._M_node, __n, __x);
  552.   }
  553.  
  554. #ifdef __STL_MEMBER_TEMPLATES
  555.  
  556.   // We don't need any dispatching tricks here, because _M_insert_after_range
  557.   // already does them.
  558.   template <class _InIter>
  559.   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
  560.     _M_insert_after_range(__pos._M_node, __first, __last);
  561.   }
  562.  
  563. #else /* __STL_MEMBER_TEMPLATES */
  564.  
  565.   void insert_after(iterator __pos,
  566.                     const_iterator __first, const_iterator __last) {
  567.     _M_insert_after_range(__pos._M_node, __first, __last);
  568.   }
  569.   void insert_after(iterator __pos,
  570.                     const value_type* __first, const value_type* __last) {
  571.     _M_insert_after_range(__pos._M_node, __first, __last);
  572.   }
  573.  
  574. #endif /* __STL_MEMBER_TEMPLATES */
  575.  
  576.   iterator insert(iterator __pos, const value_type& __x) {
  577.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  578.                                                      __pos._M_node),
  579.                     __x));
  580.   }
  581.  
  582.   iterator insert(iterator __pos) {
  583.     return iterator(_M_insert_after(__slist_previous(&this->_M_head,
  584.                                                      __pos._M_node),
  585.                                     value_type()));
  586.   }
  587.  
  588.   void insert(iterator __pos, size_type __n, const value_type& __x) {
  589.     _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),
  590.                          __n, __x);
  591.   } 
  592.     
  593. #ifdef __STL_MEMBER_TEMPLATES
  594.  
  595.   // We don't need any dispatching tricks here, because _M_insert_after_range
  596.   // already does them.
  597.   template <class _InIter>
  598.   void insert(iterator __pos, _InIter __first, _InIter __last) {
  599.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  600.                           __first, __last);
  601.   }
  602.  
  603. #else /* __STL_MEMBER_TEMPLATES */
  604.  
  605.   void insert(iterator __pos, const_iterator __first, const_iterator __last) {
  606.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  607.                           __first, __last);
  608.   }
  609.   void insert(iterator __pos, const value_type* __first, 
  610.                               const value_type* __last) {
  611.     _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 
  612.                           __first, __last);
  613.   }
  614.  
  615. #endif /* __STL_MEMBER_TEMPLATES */
  616.  
  617.  
  618. public:
  619.   iterator erase_after(iterator __pos) {
  620.     return iterator((_Node*) this->_M_erase_after(__pos._M_node));
  621.   }
  622.   iterator erase_after(iterator __before_first, iterator __last) {
  623.     return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 
  624.                                                   __last._M_node));
  625.   } 
  626.  
  627.   iterator erase(iterator __pos) {
  628.     return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, 
  629.                                                           __pos._M_node));
  630.   }
  631.   iterator erase(iterator __first, iterator __last) {
  632.     return (_Node*) this->_M_erase_after(
  633.       __slist_previous(&this->_M_head, __first._M_node), __last._M_node);
  634.   }
  635.  
  636.   void resize(size_type new_size, const _Tp& __x);
  637.   void resize(size_type new_size) { resize(new_size, _Tp()); }
  638.   void clear() { this->_M_erase_after(&this->_M_head, 0); }
  639.  
  640. public:
  641.   // Moves the range [__before_first + 1, __before_last + 1) to *this,
  642.   //  inserting it immediately after __pos.  This is constant time.
  643.   void splice_after(iterator __pos, 
  644.                     iterator __before_first, iterator __before_last)
  645.   {
  646.     if (__before_first != __before_last) 
  647.       __slist_splice_after(__pos._M_node, __before_first._M_node, 
  648.                            __before_last._M_node);
  649.   }
  650.  
  651.   // Moves the element that follows __prev to *this, inserting it immediately
  652.   //  after __pos.  This is constant time.
  653.   void splice_after(iterator __pos, iterator __prev)
  654.   {
  655.     __slist_splice_after(__pos._M_node,
  656.                          __prev._M_node, __prev._M_node->_M_next);
  657.   }
  658.  
  659.  
  660.   // Removes all of the elements from the list __x to *this, inserting
  661.   // them immediately after __pos.  __x must not be *this.  Complexity:
  662.   // linear in __x.size().
  663.   void splice_after(iterator __pos, slist& __x)
  664.   {
  665.     __slist_splice_after(__pos._M_node, &__x._M_head);
  666.   }
  667.  
  668.   // Linear in distance(begin(), __pos), and linear in __x.size().
  669.   void splice(iterator __pos, slist& __x) {
  670.     if (__x._M_head._M_next)
  671.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  672.                            &__x._M_head, __slist_previous(&__x._M_head, 0));
  673.   }
  674.  
  675.   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
  676.   void splice(iterator __pos, slist& __x, iterator __i) {
  677.     __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  678.                          __slist_previous(&__x._M_head, __i._M_node),
  679.                          __i._M_node);
  680.   }
  681.  
  682.   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
  683.   // and in distance(__first, __last).
  684.   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
  685.   {
  686.     if (__first != __last)
  687.       __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),
  688.                            __slist_previous(&__x._M_head, __first._M_node),
  689.                            __slist_previous(__first._M_node, __last._M_node));
  690.   }
  691.  
  692. public:
  693.   void reverse() { 
  694.     if (this->_M_head._M_next)
  695.       this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);
  696.   }
  697.  
  698.   void remove(const _Tp& __val); 
  699.   void unique(); 
  700.   void merge(slist& __x);
  701.   void sort();     
  702.  
  703. #ifdef __STL_MEMBER_TEMPLATES
  704.   template <class _Predicate> 
  705.   void remove_if(_Predicate __pred);
  706.  
  707.   template <class _BinaryPredicate> 
  708.   void unique(_BinaryPredicate __pred); 
  709.  
  710.   template <class _StrictWeakOrdering> 
  711.   void merge(slist&, _StrictWeakOrdering);
  712.  
  713.   template <class _StrictWeakOrdering> 
  714.   void sort(_StrictWeakOrdering __comp); 
  715. #endif /* __STL_MEMBER_TEMPLATES */
  716. };
  717.  
  718. template <class _Tp, class _Alloc>
  719. slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
  720. {
  721.   if (&__x != this) {
  722.     _Node_base* __p1 = &this->_M_head;
  723.     _Node* __n1 = (_Node*) this->_M_head._M_next;
  724.     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
  725.     while (__n1 && __n2) {
  726.       __n1->_M_data = __n2->_M_data;
  727.       __p1 = __n1;
  728.       __n1 = (_Node*) __n1->_M_next;
  729.       __n2 = (const _Node*) __n2->_M_next;
  730.     }
  731.     if (__n2 == 0)
  732.       this->_M_erase_after(__p1, 0);
  733.     else
  734.       _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 
  735.                                   const_iterator(0));
  736.   }
  737.   return *this;
  738. }
  739.  
  740. template <class _Tp, class _Alloc>
  741. void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
  742.   _Node_base* __prev = &this->_M_head;
  743.   _Node* __node = (_Node*) this->_M_head._M_next;
  744.   for ( ; __node != 0 && __n > 0 ; --__n) {
  745.     __node->_M_data = __val;
  746.     __prev = __node;
  747.     __node = (_Node*) __node->_M_next;
  748.   }
  749.   if (__n > 0)
  750.     _M_insert_after_fill(__prev, __n, __val);
  751.   else
  752.     this->_M_erase_after(__prev, 0);
  753. }
  754.  
  755. #ifdef __STL_MEMBER_TEMPLATES
  756.  
  757. template <class _Tp, class _Alloc> template <class _InputIter>
  758. void
  759. slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
  760.                                        __false_type)
  761. {
  762.   _Node_base* __prev = &this->_M_head;
  763.   _Node* __node = (_Node*) this->_M_head._M_next;
  764.   while (__node != 0 && __first != __last) {
  765.     __node->_M_data = *__first;
  766.     __prev = __node;
  767.     __node = (_Node*) __node->_M_next;
  768.     ++__first;
  769.   }
  770.   if (__first != __last)
  771.     _M_insert_after_range(__prev, __first, __last);
  772.   else
  773.     this->_M_erase_after(__prev, 0);
  774. }
  775.  
  776. #endif /* __STL_MEMBER_TEMPLATES */
  777.  
  778. template <class _Tp, class _Alloc>
  779. inline bool 
  780. operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  781. {
  782.   typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
  783.   const_iterator __end1 = _SL1.end();
  784.   const_iterator __end2 = _SL2.end();
  785.  
  786.   const_iterator __i1 = _SL1.begin();
  787.   const_iterator __i2 = _SL2.begin();
  788.   while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
  789.     ++__i1;
  790.     ++__i2;
  791.   }
  792.   return __i1 == __end1 && __i2 == __end2;
  793. }
  794.  
  795.  
  796. template <class _Tp, class _Alloc>
  797. inline bool
  798. operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
  799. {
  800.   return lexicographical_compare(_SL1.begin(), _SL1.end(), 
  801.                                  _SL2.begin(), _SL2.end());
  802. }
  803.  
  804. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  805.  
  806. template <class _Tp, class _Alloc>
  807. inline bool 
  808. operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  809.   return !(_SL1 == _SL2);
  810. }
  811.  
  812. template <class _Tp, class _Alloc>
  813. inline bool 
  814. operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  815.   return _SL2 < _SL1;
  816. }
  817.  
  818. template <class _Tp, class _Alloc>
  819. inline bool 
  820. operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  821.   return !(_SL2 < _SL1);
  822. }
  823.  
  824. template <class _Tp, class _Alloc>
  825. inline bool 
  826. operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) {
  827.   return !(_SL1 < _SL2);
  828. }
  829.  
  830. template <class _Tp, class _Alloc>
  831. inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
  832.   __x.swap(__y);
  833. }
  834.  
  835. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  836.  
  837.  
  838. template <class _Tp, class _Alloc>
  839. void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
  840. {
  841.   _Node_base* __cur = &this->_M_head;
  842.   while (__cur->_M_next != 0 && __len > 0) {
  843.     --__len;
  844.     __cur = __cur->_M_next;
  845.   }
  846.   if (__cur->_M_next) 
  847.     this->_M_erase_after(__cur, 0);
  848.   else
  849.     _M_insert_after_fill(__cur, __len, __x);
  850. }
  851.  
  852. template <class _Tp, class _Alloc>
  853. void slist<_Tp,_Alloc>::remove(const _Tp& __val)
  854. {
  855.   _Node_base* __cur = &this->_M_head;
  856.   while (__cur && __cur->_M_next) {
  857.     if (((_Node*) __cur->_M_next)->_M_data == __val)
  858.       this->_M_erase_after(__cur);
  859.     else
  860.       __cur = __cur->_M_next;
  861.   }
  862. }
  863.  
  864. template <class _Tp, class _Alloc> 
  865. void slist<_Tp,_Alloc>::unique()
  866. {
  867.   _Node_base* __cur = this->_M_head._M_next;
  868.   if (__cur) {
  869.     while (__cur->_M_next) {
  870.       if (((_Node*)__cur)->_M_data == 
  871.           ((_Node*)(__cur->_M_next))->_M_data)
  872.         this->_M_erase_after(__cur);
  873.       else
  874.         __cur = __cur->_M_next;
  875.     }
  876.   }
  877. }
  878.  
  879. template <class _Tp, class _Alloc>
  880. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
  881. {
  882.   _Node_base* __n1 = &this->_M_head;
  883.   while (__n1->_M_next && __x._M_head._M_next) {
  884.     if (((_Node*) __x._M_head._M_next)->_M_data < 
  885.         ((_Node*)       __n1->_M_next)->_M_data) 
  886.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  887.     __n1 = __n1->_M_next;
  888.   }
  889.   if (__x._M_head._M_next) {
  890.     __n1->_M_next = __x._M_head._M_next;
  891.     __x._M_head._M_next = 0;
  892.   }
  893. }
  894.  
  895. template <class _Tp, class _Alloc>
  896. void slist<_Tp,_Alloc>::sort()
  897. {
  898.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  899.     slist __carry;
  900.     slist __counter[64];
  901.     int __fill = 0;
  902.     while (!empty()) {
  903.       __slist_splice_after(&__carry._M_head,
  904.                            &this->_M_head, this->_M_head._M_next);
  905.       int __i = 0;
  906.       while (__i < __fill && !__counter[__i].empty()) {
  907.         __counter[__i].merge(__carry);
  908.         __carry.swap(__counter[__i]);
  909.         ++__i;
  910.       }
  911.       __carry.swap(__counter[__i]);
  912.       if (__i == __fill)
  913.         ++__fill;
  914.     }
  915.  
  916.     for (int __i = 1; __i < __fill; ++__i)
  917.       __counter[__i].merge(__counter[__i-1]);
  918.     this->swap(__counter[__fill-1]);
  919.   }
  920. }
  921.  
  922. #ifdef __STL_MEMBER_TEMPLATES
  923.  
  924. template <class _Tp, class _Alloc> 
  925. template <class _Predicate>
  926. void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
  927. {
  928.   _Node_base* __cur = &this->_M_head;
  929.   while (__cur->_M_next) {
  930.     if (__pred(((_Node*) __cur->_M_next)->_M_data))
  931.       this->_M_erase_after(__cur);
  932.     else
  933.       __cur = __cur->_M_next;
  934.   }
  935. }
  936.  
  937. template <class _Tp, class _Alloc> template <class _BinaryPredicate> 
  938. void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
  939. {
  940.   _Node* __cur = (_Node*) this->_M_head._M_next;
  941.   if (__cur) {
  942.     while (__cur->_M_next) {
  943.       if (__pred(((_Node*)__cur)->_M_data, 
  944.                  ((_Node*)(__cur->_M_next))->_M_data))
  945.         this->_M_erase_after(__cur);
  946.       else
  947.         __cur = (_Node*) __cur->_M_next;
  948.     }
  949.   }
  950. }
  951.  
  952. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
  953. void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
  954.                               _StrictWeakOrdering __comp)
  955. {
  956.   _Node_base* __n1 = &this->_M_head;
  957.   while (__n1->_M_next && __x._M_head._M_next) {
  958.     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
  959.                ((_Node*)       __n1->_M_next)->_M_data))
  960.       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
  961.     __n1 = __n1->_M_next;
  962.   }
  963.   if (__x._M_head._M_next) {
  964.     __n1->_M_next = __x._M_head._M_next;
  965.     __x._M_head._M_next = 0;
  966.   }
  967. }
  968.  
  969. template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 
  970. void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
  971. {
  972.   if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
  973.     slist __carry;
  974.     slist __counter[64];
  975.     int __fill = 0;
  976.     while (!empty()) {
  977.       __slist_splice_after(&__carry._M_head,
  978.                            &this->_M_head, this->_M_head._M_next);
  979.       int __i = 0;
  980.       while (__i < __fill && !__counter[__i].empty()) {
  981.         __counter[__i].merge(__carry, __comp);
  982.         __carry.swap(__counter[__i]);
  983.         ++__i;
  984.       }
  985.       __carry.swap(__counter[__i]);
  986.       if (__i == __fill)
  987.         ++__fill;
  988.     }
  989.  
  990.     for (int __i = 1; __i < __fill; ++__i)
  991.       __counter[__i].merge(__counter[__i-1], __comp);
  992.     this->swap(__counter[__fill-1]);
  993.   }
  994. }
  995.  
  996. #endif /* __STL_MEMBER_TEMPLATES */
  997.  
  998. // Specialization of insert_iterator so that insertions will be constant
  999. // time rather than linear time.
  1000.  
  1001. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1002.  
  1003. template <class _Tp, class _Alloc>
  1004. class insert_iterator<slist<_Tp, _Alloc> > {
  1005. protected:
  1006.   typedef slist<_Tp, _Alloc> _Container;
  1007.   _Container* container;
  1008.   typename _Container::iterator iter;
  1009. public:
  1010.   typedef _Container          container_type;
  1011.   typedef output_iterator_tag iterator_category;
  1012.   typedef void                value_type;
  1013.   typedef void                difference_type;
  1014.   typedef void                pointer;
  1015.   typedef void                reference;
  1016.  
  1017.   insert_iterator(_Container& __x, typename _Container::iterator __i) 
  1018.     : container(&__x) {
  1019.     if (__i == __x.begin())
  1020.       iter = __x.before_begin();
  1021.     else
  1022.       iter = __x.previous(__i);
  1023.   }
  1024.  
  1025.   insert_iterator<_Container>&
  1026.   operator=(const typename _Container::value_type& __value) { 
  1027.     iter = container->insert_after(iter, __value);
  1028.     return *this;
  1029.   }
  1030.   insert_iterator<_Container>& operator*() { return *this; }
  1031.   insert_iterator<_Container>& operator++() { return *this; }
  1032.   insert_iterator<_Container>& operator++(int) { return *this; }
  1033. };
  1034.  
  1035. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1036.  
  1037. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1038. #pragma reset woff 1174
  1039. #pragma reset woff 1375
  1040. #endif
  1041.  
  1042. __STL_END_NAMESPACE 
  1043.  
  1044. #endif /* __SGI_STL_INTERNAL_SLIST_H */
  1045.  
  1046. // Local Variables:
  1047. // mode:C++
  1048. // End:
  1049.